package com.liyunhan.StrassenAlgorithm;

import java.util.ArrayList;

/**
 * @Description: 优化Strassen算法, 使得可以计算任意偶数的矩阵乘法
 * @Author: Liyunhan
 * @Date: 2021/11/16 0:00
 */
public class OptimStrassen extends MyStrassen {
    //用于存放小矩阵(子矩阵)
    private ArrayList<double[][]> subMatrixList1 = new ArrayList<>();
    private ArrayList<double[][]> subMatrixList2 = new ArrayList<>();
    //用于存放结果矩阵(子矩阵)
    private ArrayList<double[][]> resSubMatrixList = new ArrayList<>();


    public OptimStrassen(int n, double[][] matrix1, double[][] matrix2) {
        super(n, matrix1, matrix2);
    }

    /**
     * @ "方法重写"
     * 先根据矩阵的大小对矩阵进行预处理.
     * 对于任一偶数n,总有n = m * 2^k, 将矩阵分为m*m个的2^k阶矩阵.
     * 小矩阵用Strassen相乘, 大矩阵用传统算法.
     */
    @Override
    public void execAlgorithm() {
        int n = this.getN();
        //记录小矩阵的阶数
        int k = 1;
        while (n % 2 == 0) {
            n /= 2;
            k *= 2;
        }
        //为子矩阵赋值
        //初始化第一个矩阵的子矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                subMatrixList1.add(new double[k][k]);
            }
        }
        //为第一个矩阵的子矩阵赋值
        this.copyValues(subMatrixList1, this.getMatrix1(), k);

        //初始化第二个矩阵的子矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                subMatrixList2.add(new double[k][k]);
            }
        }
        //为第二个矩阵的子矩阵赋值
        this.copyValues(subMatrixList2, this.getMatrix2(), k);

        //矩阵乘法
        //初始化结果子矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                resSubMatrixList.add(new double[k][k]);
            }
        }

        for (int m = 0; m < n; m++) {
            for (int i = 0; i < n; i++) {
                this.strassenMutipleMatrix(k, this.subMatrixList1.get(i), this.subMatrixList2.get(m + i * n),
                        this.resSubMatrixList.get(i));
            }
        }
        //乘法结束后将子矩阵拼接为结果矩阵
        for (int i = 0; i < this.getN(); i += k) {
            for (int j = 0; j < this.getN(); j += k) {
                for (int l = 0; l < k; l++) {
                    for (int m = 0; m < k; m++) {
                        this.getResMatrix()[i][j] = this.resSubMatrixList.get(i)[l][m];
                    }
                }
            }

        }
    }

    /**
     * 矩阵赋值通用操作
     *
     * @param k
     */
    public void copyValues(ArrayList<double[][]> arrayList, double[][] matrix, int k) {
        int count = 0;
        //列累加器
        int col = 0;
        //行累加器
        int row = 0;
        for (int i = 0; i < this.getN(); i += k) {
            for (int j = 0; j < this.getN(); j += k) {
                for (int l = i; l < k; l++) {
                    for (int m = j; m < k; m++) {
                        if (col < k) {
                            arrayList.get(count)[row][col++] = matrix[l][m];
                        } else {
                            col = 0;
                            arrayList.get(count)[++row][col++] = matrix[l][m];
                        }
                    }
                }
                //计数器归0
                row = col = 0;
                count++;
            }
        }
    }
}
